package com.shiguiwu.springmybatis.leetcode;

import cn.hutool.core.util.ArrayUtil;
import cn.hutool.core.util.StrUtil;
import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import java.util.regex.Pattern;

/**
 * @description: 力扣算法涮题
 * @author: stone
 * @date: Created by 2022/5/27 16:18
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.leetcode
 */
@Slf4j
public class LeetCodeTest {

    public static void main(String[] args) {
        //String s = validIPAddressV2("127.0.101.1");
        //log.info("得到的值是 ===> {}", s);
        //int[] a = {332484035, 524908576, 855865114, 632922376, 222257295, 690155293, 112677673, 679580077, 337406589, 290818316, 877337160, 901728858, 679284947, 688210097, 692137887, 718203285, 629455728, 941802184};
        //minEatingSpeed(a, 823855818);

//        int[] a = {1, 3, 1, 5, 4};
//        findPairs(a, 0);
        String iPaddr = defangIPaddr("172.0.0.1");
        log.info("得到的值是 ===> {}", iPaddr);

    }


    /**
     * /(\d+)\.(\d+)\.(\d+)\.(\d+)/g //
     * 给定一个字符串 queryIP。如果是有效的 IPv4 地址，返回 "IPv4" ；如果是有效的 IPv6 地址，返回 "IPv6" ；如果不是上述类型的 IP 地址，返回 "Neither" 。
     * <p>
     * 有效的IPv4地址 是 “x1.x2.x3.x4” 形式的IP地址。 其中 0 <= xi <= 255 且 xi 不能包含 前导零。例如: “192.168.1.1” 、 “192.168.1.0” 为有效IPv4地址， “192.168.01.1” 为无效IPv4地址; “192.168.1.00” 、 “192.168@1.1” 为无效IPv4地址。
     *
     * @param queryIP input ip
     * @return type
     * <p>
     * 2001:0db8:85a3:033:0:8A2E:0370:7334 true
     */

    public static Pattern piv4_pattern = Pattern.compile("(\\d{1,3})\\.(\\d{1,3})\\.(\\d{1,3})\\.(\\d{1,3})");
    public static Pattern piv6_pattern = Pattern.compile("([a-fA-F0-9]{1,4}):([a-fA-F0-9]{1,4}):([a-fA-F0-9]{1,4}):([a-fA-F0-9]{1,4}):([a-fA-F0-9]{1,4}):([a-fA-F0-9]{1,4}):([a-fA-F0-9]{1,4}):([a-fA-F0-9]{1,4})");
    public static String validIPAddress(String queryIP) {

        if (queryIP.contains(".")) {
            String[] split = queryIP.split("\\.");
            if (split.length != 4 || !piv4_pattern.matcher(queryIP).matches()) {
                return "Neither";
            }

            for (String item : split) {

                //Matcher matcher = piv4_pattern.matcher(item);
                //if (!matcher.matches()) {
                //    return "Neither";
                //}
                if (item.length() > 1 && item.startsWith("0")) {
                    return "Neither";
                }

                int parseInt = Integer.parseInt(item);
                if (parseInt < 0 || parseInt > 255) {
                    return "Neither";
                }


            }

            return "IPv4";

        }

        if (queryIP.contains(":")) {
            String[] split = queryIP.split(":");
            if (split.length != 8 || !piv6_pattern.matcher(queryIP).matches()) {
                return "Neither";
            }


            return "IPv6";
        }

        return "Neither";
    }


    //网友的题目
    //    String first = "(\\d | [1-9]\\d  |  1\\d{2}   |  2[0-4]\\d   |25[0-5])";
    //        String regex = first + "(\\." + first +"){3}";
    public static String validIPAddressV2(String IP) {
        if (IP == null) {
            return "Neither";
        }

        String regex0 = "(\\d|[1-9]\\d|1\\d\\d|2[0-4]\\d|25[0-5])";
        String regexIPv4 = regex0 + "(\\." + regex0 + "){3}";
        String regex1 = "([\\da-fA-F]{1,4})";
        String regexIPv6 = regex1 + "(:" + regex1 + "){7}";

        String result = "Neither";
        if (IP.matches(regexIPv4)) {
            result = "IPv4";
        } else if (IP.matches(regexIPv6)) {
            result = "IPv6";
        }
        return result;
    }





    /**
     * 先序遍历的应用
     *
     * @param t1
     * @param t2
     * @return
     */
    public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) {

        if (t1 == null && t2 == null) {
            return null;
        }
        // 先合并根节点
        TreeNode root = new TreeNode((t1 == null ? 0 : t1.val) + (t2 == null ? 0 : t2.val));
        // 再递归合并左右子树
        root.left = mergeTrees(t1 == null ? null : t1.left, t2 == null ? null : t2.left);
        root.right = mergeTrees(t1 == null ? null : t1.right, t2 == null ? null : t2.right);
        return root;
    }

    public static void minOrder(TreeNode root) {
        log.info("输出的节点未===>{}", root.val);

        while (root.left != null) {
            //log.info("输出的节点未===>{}", root.left.val);
            minOrder(root.left);

        }


        while (root.right != null) {
            //log.info("输出的节点未===>{}", root.right.val);
            minOrder(root.right);
        }
    }


    /**
     * 珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
     * <p>
     * 珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  
     * <p>
     * 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
     * <p>
     * 返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
     *
     * @param piles
     * @param h
     * @return
     */
    public static int minEatingSpeed(int[] piles, int h) {
        long t = h + 1;
        int k = 1;
        for (int pile : piles) {
            k = Math.max(k, pile);
        }

        int min = 1;
        while (t > h) {
            t = 0;
            int mid = min + (k - min) / 2;
            for (int pile : piles) {
                if (k >= pile) {
                    t++;
                } else {
                    t += (pile % k == 0 ? pile / k : pile / k + 1);
                }
            }

            if (t <= h) {
                break;
            }
            min = mid + 1;
        }

        log.info("可以在 h 小时内吃掉所有香蕉的最小速度 k = {}", k);
        return k;
    }


    public int minEatingSpeedV2(int[] piles, int h) {
        int min = 1;
        int max = 0;
        for (int pile : piles) {
            max = Math.max(max, pile);
        }

        while (min < max) {
            int mid = min + (max - min) / 2;
            //如果获取时间超时，说明速度太慢
            if (getTime(piles, mid) > h) {
                min = mid + 1;
            } else {
                max = mid;
            }

        }
        return max;
    }

    //获取当前速度所需要时间
    public int getTime(int[] piles, int speed) {
        int time = 0;
        for (int pile : piles) {
            if (pile <= speed) {
                time++;
            } else {
                time += pile % speed == 0 ? pile / speed : pile / speed + 1;
            }
        }
        return time;
    }

    /**
     * 学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。
     * <p>
     * 排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是预计排在这一行中第 i 位的学生的高度（下标从 0 开始）。
     * <p>
     * 给你一个整数数组 heights ，表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度（下标从 0 开始）。
     * <p>
     * 返回满足 heights[i] != expected[i] 的 下标数量 。
     *
     * @param heights
     * @return 输入：heights = [1,1,4,2,1,3]
     * 输出：3
     * 解释：
     * 高度：[1,1,4,2,1,3]
     * 预期：[1,1,1,2,3,4]
     * 下标 2 、4 、5 处的学生高度不匹配。
     */
    public static int heightChecker(int[] heights) {
        if (ArrayUtil.isEmpty(heights)) {
            return 0;
        }
        int t = 0;
        int[] temps = new int[heights.length];
        System.arraycopy(heights, 0, temps, 0, heights.length);
        int y = 0;
        for (int i = 0; i < temps.length - 1; i++) {
            for (int j = 0; j < temps.length - 1 - i; j++) {
                if (temps[j] > temps[j + 1]) {
                    y = temps[j];
                    temps[j] = temps[j + 1];
                    temps[j + 1] = y;
                }
            }
        }


        for (int i = 0; i < temps.length; i++) {
            if (temps[i] != heights[i]) {
                t++;
            }
        }

        return t;
    }


    public static int heightCheckerV2(int[] heights) {

        int t = 0;
        int[] temps = heights.clone();
        //System.arraycopy(heights, 0, temps, 0, heights.length);

        Arrays.sort(temps);

        for (int i = 0; i < temps.length; i++) {
            if (temps[i] != heights[i]) {
                t++;
            }
        }

        return t;
    }


    /**
     * 给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
     * 原意就是二维数组的对角线遍历
     *
     * @param matrix 二维数组
     * @return res
     */
    public int[] findDiagonalOrder(int[][] matrix) {
        int r = 0, c = 0;
        int row = matrix.length, col = matrix[0].length;
        int[] res = new int[row * col];
        for (int i = 0; i < res.length; i++) {
            res[i] = matrix[r][c];
            // r + c 即为遍历的层数，偶数向上遍历，奇数向下遍历
            if ((r + c) % 2 == 0) {
                if (c == col - 1) {
                    // 往下移动一格准备向下遍历
                    r++;
                } else if (r == 0) {
                    // 往右移动一格准备向下遍历
                    c++;
                } else {
                    // 往上移动
                    r--;
                    c++;
                }
            } else {
                if (r == row - 1) {
                    // 往右移动一格准备向上遍历
                    c++;
                } else if (c == 0) {
                    // 往下移动一格准备向上遍历
                    r++;
                } else {
                    // 往下移动
                    r++;
                    c--;
                }
            }
        }
        return res;
    }

    /**
     * 数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
     * <p>
     * 给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。
     * 这个在leetcode过不了，暴力破解
     */
    public int smallestDistancePair(int[] nums, int k) {
        int length = nums.length;
        int t = 0;
        int[] ks = new int[length * (length - 1) / 2];

        for (int i = 0; i < length - 1; i++) {
            for (int j = i + 1; j < length; j++) {
                ks[t] = Math.abs(nums[i] - nums[j]);
                t++;
            }
        }

        Arrays.sort(ks);

        return ks[k - 1];
    }

    public int smallestDistancePairV2(int[] nums, int k) {
        //先排序
        Arrays.sort(nums);

        int len = nums.length;
        //排序完成后，距离距离最小和最大都出来了
        int min = nums[0], max = nums[len - 1] - min;

        while (min <= max) {

            //中间距离
            int mid = min + max;

            // 判断 距离差 <= mid 的数对的数量
            // 即 nums[j] - nums[i] <= mid 的数对的数量
            // 也就是说找 nums[j] - mid <= nums[i] 的数对的数量

            int totalCount = 0;
            for (int j = 0; j < nums.length; j++) {
                //0, 2 - 4
                int count = getCount(nums, j, nums[j] - mid);
                totalCount += count;
            }
            if (totalCount >= k) {
                // 距离差取 mid 时，数对数量 >= k，那么说明 k 可能在 mid 左边
                max = mid - 1;
            } else {
                // 距离差取 mid 时，数对数量 < k，那么说明 k 必然在 mid 右边
                min = mid + 1;
            }
        }
        return min;
    }

    /**
     * 获取 nums[i] >= numsi
     * 也就是 nums[i] >= nums[j] - mid 的数量
     * 其中 i < j
     */
    private int getCount(int[] nums, int j, int numsi) {
        // 二分查找 nums[i] >= numsi 的最小下标
        int min = 0;
        int max = j;

        while (min <= max) {
            int mid = (min + max) / 2;
            if (nums[mid] < numsi) {
                // nums[mid] 比 numsi 还要小，说明 i 必然在 mid 后面
                min = mid + 1;
            } else {
                // nums[mid] 比 numsi 要大或者相同，说明 i 可能在 mid 前面
                max = mid - 1;
            }
        }

        // min 就是 nums[i] >= numsi 的最小下标
        return j - min;
    }


    /**
     * 给定一个整数数组和一个整数 k，你需要在数组里找到 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。
     * <p>
     * 其实题意就是数组中两两组合，求差为k的个数
     *
     * @param nums
     * @param k
     * @return
     */
    public static int findPairs(int[] nums, int k) {
        //Arrays.sort(nums);
        Map<Integer, Integer> hashMap = new HashMap<>(nums.length);
        Arrays.stream(nums).forEach(e -> hashMap.compute(e, (k1, v) -> v == null ? 1 : ++v));

        Set<Map.Entry<Integer, Integer>> entries = hashMap.entrySet();
        int count = 0;
        for (Map.Entry<Integer, Integer> next : entries) {
            if (k == 0) {
                if (next.getValue() > 1) {
                    count++;
                }

            } else if (hashMap.containsKey(next.getKey() + k)) {
                count++;
            }
        }

        return count;
    }


    /**
     * DP 贪心思路 7ms 时间复杂度O(n) 因为要求当前最小的翻转使得单调递增 因为只存在于 0 1,     动态规划算法
     * <p>
     * ⭐ 那么如果顺序遍历到当前字符为 1 时，此时不会对结果产生贡献，
     * <p>
     * 但是如果顺序遍历到当前字符为 0 时 , 有两种情况：
     * 】=
     * 1️⃣ 如果需要保留当前 这个 0 则需要将其前面所有出现的 1 都要进行翻转置为 0 保证当前出现 0 的前面全部为 0
     * <p>
     * 2️⃣ 将当前这个 0 置为 1 即当前需要翻转的翻转次数 + 1
     * <p>
     * 上述两种情况显然取最小 ，依次顺序遍历 求取贡献度 遍历完成 即完成 故时间复杂度为 O(n)
     */
    public static int minFlipsMonoIncr(String s) {
        char[] cs = s.toCharArray();
        int n = s.length();
        int res = 0, curOneCnt = 0;
        for (int i = 0; i < n; i++) {
            if (cs[i] == '1') {
                curOneCnt++;
            } else {
                res = Math.min(res + 1, curOneCnt);
            }
        }
        return res;
    }


    /**
     * 给你一个有效的 IPv4 地址 address，返回这个 IP 地址的无效化版本。
     * <p>
     * 所谓无效化 IP 地址，其实就是用 "[.]" 代替了每个 "."。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * 输入：address = "1.1.1.1"
     * 输出："1[.]1[.]1[.]1"
     * 示例 2：
     * <p>
     * 输入：address = "255.100.50.0"
     * 输出："255[.]100[.]50[.]0"
     *
     * @param address
     * @return
     */
    public static String defangIPaddr(String address) {

        return address.replaceAll("\\.", "[.]");
    }


    /**
     * 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
     * <p>
     * 假设二叉树中至少有一个节点。
     * <p>
     * <p>
     * 前序遍历，把拟最深层，左边的节点下来，不断更新 max < depth 很精髓，同一层深度的节点，由于前序遍历只会记录最左边的
     *
     * @param root
     * @return
     */
    int max = -1;
    int res = 0;

    public int findBottomLeftValue(TreeNode root) {

        dfs(root, 0);
        return res;
    }

    void dfs(TreeNode node, int depth) {
        if (node != null) {
            if (node.left == null && node.right == null) {
                if (max < depth) {
                    max = depth;
                    res = node.val;
                }
            }
            dfs(node.left, depth + 1);
            dfs(node.right, depth + 1);
        }


    }


    /**
     * 设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
     * <p>
     * 实现 MagicDictionary 类：
     * <p>
     * MagicDictionary() 初始化对象
     * void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
     * bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。
     */


    static class MagicDictionary {
        Set<String> dic = null;
        public MagicDictionary() {
            dic = new HashSet<>();
        }

        public void buildDict(String[] dictionary) {
            dic.addAll(Arrays.asList(dictionary));
        }

        public boolean search(String searchWord) {
            for (String str : dic) {
                if (this.checkLength(str, searchWord) && this.checkDiff(str, searchWord)) {
                    return true;
                }
            }
            return false;
        }

        /**
         * 长度一定要相等，且不能是null
         * @param src
         * @param target
         * @return
         */
        private boolean checkLength(String src, String target) {
            return !StrUtil.hasBlank(src) &&
                    src.length() == target.length() &&
                    !src.equalsIgnoreCase(target);
        }

        /**
         * 变化一个字符，是否和已知的字符串相等.
         * 换句话说就是只有一个字符串不一样而已
         * @param src
         * @param target
         * @return
         */
        private boolean checkDiff(String src, String target) {
            int diff = 0;
            for (int i = 0; i < src.length(); i++) {
                if (src.charAt(i) != target.charAt(i)) {
                    diff++;
                }

                if (diff > 1) {
                    return false;
                }
            }

            return diff == 1;

        }
    }


    /**
     * 给定一个整数数组 asteroids，表示在同一行的行星。
     *
     * 对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。
     *
     * 找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
     *
     *
     *
     * 输入：asteroids = [5,10,-5]
     * 输出：[5,10]
     * 解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
     * @param asteroids
     * @return
     * todo 有问题的编程
     */
    public static int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int asteroid : asteroids) {
            if (asteroid < 0) {
                if (!stack.empty() && stack.peek() > 0) {
                    while (!stack.empty()) {
                        if (stack.peek() < 0) {
                            stack.push(asteroid);
                        }

                        if (Math.abs(asteroid) > stack.peek()) {
                            if (stack.size() == 1) {
                                stack.pop();
                                stack.push(asteroid);
                                break;
                            }
                            else {
                                stack.pop();
                            }

                        }
                        //那就是绝对相等，那就没有了
                        else if(Math.abs(asteroid) == stack.peek()){
                            stack.pop();
                            break;
                        }
                        else{
                            break;
                        }

                    }
                }
            }
            else {

                stack.push(asteroid);
            }
        }

        int[] res = new int[stack.size()];
        for (int i = 0; i < stack.size(); i++) {
            res[i] = stack.get(i);
        }
        return res;
    }

}
